# ์ฝ์ ์ ๋ ฌ(Insertion Sort)
# Goal
- Insertion Sort์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Insertion Sort ๊ณผ์ ์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
- Insertion Sort์ ๊ตฌํํ ์ ์๋ค.
- Insertion Sort์ ์๊ฐ๋ณต์ก๋์ ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ๊ณ์ฐํ ์ ์๋ค.
- Insertion Sort์ Selection Sort ์ฐจ์ด์ ๋ํด ์ค๋ช ํ ์ ์๋ค.
# Abstract
์ ์์ ์นด๋๋ฅผ ์ ๋ ฌํ๋ ๋ฐฉ๋ฒ๊ณผ ์ ์ฌํ๋ค.
Insertion Sort๋ Selection Sort์ ์ ์ฌํ์ง๋ง, ์ข ๋ ํจ์จ์ ์ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
Insertion Sort๋ 2๋ฒ์งธ ์์๋ถํฐ ์์ํ์ฌ ๊ทธ ์(์ผ์ชฝ)์ ์์๋ค๊ณผ ๋น๊ตํ์ฌ ์ฝ์ ํ ์์น๋ฅผ ์ง์ ํ ํ, ์์๋ฅผ ๋ค๋ก ์ฎ๊ธฐ๊ณ ์ง์ ๋ ์๋ฆฌ์ ์๋ฃ๋ฅผ ์ฝ์ ํ์ฌ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ต์ ์ ๊ฒฝ์ฐ O(N)์ด๋ผ๋ ์์ฒญ๋๊ฒ ๋น ๋ฅธ ํจ์จ์ฑ์ ๊ฐ์ง๊ณ ์์ด, ๋ค๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ผ๋ถ๋ก ์ฌ์ฉ๋ ๋งํผ ์ข์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
# Process (Ascending)
- ์ ๋ ฌ์ 2๋ฒ์งธ ์์น(index)์ ๊ฐ์ temp์ ์ ์ฅํ๋ค.
- temp์ ์ด์ ์ ์๋ ์์๋ค๊ณผ ๋น๊ตํ๋ฉฐ ์ฝ์ ํด๋๊ฐ๋ค.
- '1'๋ฒ์ผ๋ก ๋์๊ฐ ๋ค์ ์์น(index)์ ๊ฐ์ temp์ ์ ์ฅํ๊ณ , ๋ฐ๋ณตํ๋ค.
# Java Code (Ascending)
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}
์ฒซ ๋ฒ์งธ ์์ ์(์ผ์ชฝ)์๋ ์ด๋ค ์์๋ ๊ฐ๊ณ ์์ง ์๊ธฐ ๋๋ฌธ์, ๋ ๋ฒ์งธ ์์น(index)๋ถํฐ ํ์์ ์์ํ๋ค. temp์ ์์๋ก ํด๋น ์์น(index) ๊ฐ์ ์ ์ฅํ๊ณ , prev์๋ ํด๋น ์์น(index)์ ์ด์ ์์น(index)๋ฅผ ์ ์ฅํ๋ค.
์ด์ ์์น(index)๋ฅผ ๊ฐ๋ฆฌํค๋ prev๊ฐ ์์๊ฐ ๋์ง ์๊ณ , ์ด์ ์์น(index)์ ๊ฐ์ด '1'๋ฒ์์ ์ ํํ ๊ฐ๋ณด๋ค ํฌ๋ค๋ฉด, ์๋ก ๊ฐ์ ๊ตํํด์ฃผ๊ณ prev๋ฅผ ๋ ์ด์ ์์น(index)๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ํ๋ค.
'2'๋ฒ์์ ๋ฐ๋ณต๋ฌธ์ด ๋๋๊ณ ๋ ๋ค, prev์๋ ํ์ฌ temp ๊ฐ๋ณด๋ค ์์ ๊ฐ๋ค ์ค ์ ์ผ ํฐ ๊ฐ์ ์์น(index) ๋ฅผ ๊ฐ๋ฆฌํค๊ฒ ๋๋ค. ๋ฐ๋ผ์, (prev+1)์ temp ๊ฐ์ ์ฝ์ ํด์ค๋ค.
# GIF๋ก ์ดํดํ๋ Insertion Sort
# ์๊ฐ๋ณต์ก๋
์ต์
์ ๊ฒฝ์ฐ(์ญ์ผ๋ก ์ ๋ ฌ๋์ด ์์ ๊ฒฝ์ฐ) Selection Sort์ ๋ง์ฐฌ๊ฐ์ง๋ก, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
์ฆ, O(n^2) ์ด๋ค.
ํ์ง๋ง, ๋ชจ๋ ์ ๋ ฌ์ด ๋์ด์๋ ๊ฒฝ์ฐ(Optimal)ํ ๊ฒฝ์ฐ, ํ๋ฒ์ฉ ๋ฐ์ ๋น๊ต๋ฅผ ์ํ๋ฏ๋ก O(n) ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ฒ ๋๋ค. ๋ํ, ์ด๋ฏธ ์ ๋ ฌ๋์ด ์๋ ๋ฐฐ์ด์ ์๋ฃ๋ฅผ ํ๋์ฉ ์ฝ์ /์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์๋, ํ์ค์ ์ผ๋ก ์ต๊ณ ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด ๋๋๋ฐ, ํ์์ ์ ์ธํ ์ค๋ฒํค๋๊ฐ ๋งค์ฐ ์ ๊ธฐ ๋๋ฌธ์ด๋ค.
์ต์ ์ ๊ฒฝ์ฐ๋ O(n) ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๊ณ , ํ๊ท ๊ณผ ์ต์ ์ ๊ฒฝ์ฐ O(n^2) ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๊ฒ ๋๋ค.
# ๊ณต๊ฐ๋ณต์ก๋
์ฃผ์ด์ง ๋ฐฐ์ด ์์์ ๊ตํ(swap)์ ํตํด, ์ ๋ ฌ์ด ์ํ๋๋ฏ๋ก O(n) ์ด๋ค.
# ์ฅ์
์๊ณ ๋ฆฌ์ฆ์ด ๋จ์ํ๋ค.
๋๋ถ๋ถ์ ์์๊ฐ ์ด๋ฏธ ์ ๋ ฌ๋์ด ์๋ ๊ฒฝ์ฐ, ๋งค์ฐ ํจ์จ์ ์ผ ์ ์๋ค.
์ ๋ ฌํ๊ณ ์ ํ๋ ๋ฐฐ์ด ์์์ ๊ตํํ๋ ๋ฐฉ์์ด๋ฏ๋ก, ๋ค๋ฅธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ํ์๋ก ํ์ง ์๋๋ค. => ์ ์๋ฆฌ ์ ๋ ฌ(in-place sorting)
์์ ์ ๋ ฌ(Stable Sort) ์ด๋ค.
Selection Sort๋ Bubble Sort๊ณผ ๊ฐ์ O(n^2) ์๊ณ ๋ฆฌ์ฆ์ ๋น๊ตํ์ฌ ์๋์ ์ผ๋ก ๋น ๋ฅด๋ค.
# ๋จ์
ํ๊ท ๊ณผ ์ต์ ์ ์๊ฐ๋ณต์ก๋๊ฐ O(n^2)์ผ๋ก ๋นํจ์จ์ ์ด๋ค.
Bubble Sort์ Selection Sort์ ๋ง์ฐฌ๊ฐ์ง๋ก, ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ ๊ธธ์ด์ง์๋ก ๋นํจ์จ์ ์ด๋ค.
# Conclusion
Selection Sort์ Insertion Sort๋ k๋ฒ์งธ ๋ฐ๋ณต ์ดํ, ์ฒซ๋ฒ์งธ k ์์๊ฐ ์ ๋ ฌ๋ ์์๋ก ์จ๋ค๋ ์ ์์ ์ ์ฌํ๋ค. ํ์ง๋ง, Selection Sort๋ k+1๋ฒ์งธ ์์๋ฅผ ์ฐพ๊ธฐ ์ํด ๋๋จธ์ง ๋ชจ๋ ์์๋ค์ ํ์ํ์ง๋ง Insertion Sort๋ k+1๋ฒ์งธ ์์๋ฅผ ๋ฐฐ์นํ๋ ๋ฐ ํ์ํ ๋งํผ์ ์์๋ง ํ์ํ๊ธฐ ๋๋ฌธ์ ํจ์ฌ ํจ์จ์ ์ผ๋ก ์คํ๋๋ค๋ ์ฐจ์ด๊ฐ ์๋ค.